package j2024.j202410;

public class j1026 {
    /**
     * 106. 从中序与后序遍历序列构造二叉树
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
     * postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     */
    int postindex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postindex = postorder.length-1;
        return buildTreeChild(inorder,postorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int begin,int end) {
        if(begin>=end){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postindex]);
        int index = findRoot(inorder,begin,end,postorder[postindex]);
        postindex--;
        root.right = buildTreeChild(inorder,postorder,index+1,end);

        root.left = buildTreeChild(inorder,postorder,begin,index-1);
        return root;
    }
    public int findRoot(int[] inorder,int begin,int end,int key) {
        for (int i = begin; i <= end; i++) {
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }
}
